package no.hib.dat102.mengde.kjedet;

import no.hib.dat102.mengde.adt.*;

//********************************************************************
// Kjedet implementasjon av en mengde. 
//********************************************************************
import java.util.*;

public class KjedetMengde<T> implements MengdeADT<T> {
	private static Random rand = new Random();
	private int antall; // antall elementer i mengden
	private LinearNode<T> start;

	/**
	 * Oppretter en tom mengde.
	 */
	public KjedetMengde() {
		antall = 0;
		start = null;
	}

	@Override
	public void leggTil(T element) {
		if (!(inneholder(element))) {
			LinearNode<T> ny = new LinearNode<>(element);
			ny.setNeste(start);
			start = ny;
			antall++;
		}
	}

	@Override
	public void leggTilAlle(MengdeADT<T> m2) {
		Iterator<T> teller = m2.oppramser();
		while (teller.hasNext()) {
			leggTil(teller.next());
		}
	}

	@Override
	public T fjernTilfeldig() {
		LinearNode<T> forgjenger, aktuell;
		T resultat = null;
		if (!erTom()) {
			int valg = rand.nextInt(antall) + 1;
			if (valg == 1) {
				resultat = start.getElement();
				start = start.getNeste();
			} else {
				forgjenger = start;
				for (int nr = 2; nr < valg; nr++) {
					forgjenger = forgjenger.getNeste();
				}
				aktuell = forgjenger.getNeste();
				resultat = aktuell.getElement();
				forgjenger.setNeste(aktuell.getNeste());
			}
			antall--;
		}// if
		return resultat;
	}//

	@Override
	public T fjern(T element) {
		boolean funnet = false;
		LinearNode<T> forgjenger, aktuell = null;
		T resultat = null;
		if (!erTom()) {
			if (start.getElement().equals(element)) {// Sletter foran
				resultat = start.getElement();
				start = start.getNeste();
				antall--;
			} else { // Gjennomg�r den kjedete strukturen
				forgjenger = start;
				aktuell = start.getNeste();
				for (int sok = 1; sok < antall && !funnet; sok++) {
					if (aktuell.getElement().equals(element))
						funnet = true;
					else {
						forgjenger = aktuell;
						aktuell = aktuell.getNeste();
					}
				}
				if (funnet) {
					resultat = aktuell.getElement(); // Sletter midt inni eller
					// bak
					forgjenger.setNeste(aktuell.getNeste());
					antall--;
				}
			}// if �else
		}// if ikke-tom
		return resultat;
	}//

	// ny

	@Override
	public boolean inneholder(T element) {
		boolean funnet = false;
		LinearNode<T> aktuell = start;
		for (int sok = 0; sok < antall && !funnet; sok++) {
			if (aktuell.getElement().equals(element))
				funnet = true;
			else
				aktuell = aktuell.getNeste();
		}
		return funnet;
	}

	@Override
	public boolean erLik(MengdeADT<T> m2) {
		boolean likeMengder = true;
		T element = null;
		if (antall() == m2.antall()) {
			Iterator<T> teller = m2.oppramser();
			while (teller.hasNext() && likeMengder) {
				element = teller.next();
				if (!this.inneholder(element)) {
					likeMengder = false;
				}// if
			}// while
		}// if
		else {
			likeMengder = false;
		}
		return likeMengder;
	}

	@Override
	public boolean erTom() {
		return (antall() == 0);
	}

	@Override
	public int antall() {
		return antall;
	}

	@Override
	public Iterator<T> oppramser() {
		return new KjedetIterator<T>(start);
	}

	@Override
	public MengdeADT<T> snitt(MengdeADT<T> m2) {
		KjedetMengde<T> snittMengde = new KjedetMengde<T>();
		T element;
		Iterator<T> teller = m2.oppramser();
		while (teller.hasNext()) {
			element = teller.next();
			if (this.inneholder(element)) {
				snittMengde.settInn(element);
			}
		}
		return snittMengde;

	}

	@Override
	public MengdeADT<T> differans(MengdeADT<T> m2) {
		KjedetMengde<T> differansMengde = new KjedetMengde<T>();
		T element;
		Iterator<T> itererer = this.oppramser();
		while (itererer.hasNext()) {
			element = itererer.next();
			if (!m2.inneholder(element)) {
				differansMengde.settInn(element);
			}
		}

		return differansMengde;
	}

	private void settInn(T nyElem) {
		LinearNode<T> nyNode = new LinearNode<T>(nyElem);
		nyNode.setNeste(start);
		start = nyNode;
		antall++;
	}

	@Override
	public MengdeADT<T> union(MengdeADT<T> m2) {
		KjedetMengde<T> begge = new KjedetMengde<T>();
		LinearNode<T> aktuell = start;
		while (aktuell != null) {
			begge.settInn(aktuell.getElement());
			aktuell = aktuell.getNeste();
		}// while

		Iterator<T> teller = m2.oppramser();
		while (teller.hasNext()) {
			T element = teller.next();
			if (!inneholder(element)) {
				begge.settInn(element);
			}
		}
		return begge;
	}

}// class
